package com.c2b.algorithm.leetcode.jzoffer;

/**
 * <a href="https://www.nowcoder.com/practice/6fe361ede7e54db1b84adc81d09d8524?tpId=13&&tqId=11203&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking">数组中重复的数字</a>
 * <p>在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。<br>
 * 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1</p>
 * <P>数据范围：0≤n≤10000 进阶：时间复杂度O(n) ，空间复杂度O(n) </P>
 *
 * @author c2b
 * @since 2023/3/8 14:12
 */
public class JzOffer0003Duplicate {

    /**
     * 在原数组上进行数组重排
     *
     * @param numbers int整型一维数组
     * @return int整型
     */
    public int duplicate(int[] numbers) {
        if (numbers == null || numbers.length <= 1) {
            return -1;
        }
        int currIndex = 0;
        while (currIndex < numbers.length) {
            // 当前数组下标对应的值和下标恰好相等
            if (currIndex == numbers[currIndex]) {
                currIndex++;

            } else {
                // i位置上的值
                int val = numbers[currIndex];
                // i位置上的值作为下标对应数组上的值
                if (val == numbers[val]) {
                    return val;
                } else {
                    // 交换
                    int temp = numbers[currIndex];
                    numbers[currIndex] = numbers[val];
                    numbers[val] = temp;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        JzOffer0003Duplicate jzOffer0003Duplicate = new JzOffer0003Duplicate();
        int duplicate = jzOffer0003Duplicate.duplicate(new int[]{2, 3, 1, 0, 2, 5, 3});
    }
}
